package main.面试金典第六版;

import java.util.*;

public class Interview04 {
    public static void main(String[] args) {
        System.out.println("面试题04.01：节点间通路");
        System.out.println("面试题04.02：最小高度树");
        System.out.println("面试题04.03：特定深度节点链表");
        System.out.println("面试题04.04：检查平衡性");
        System.out.println("面试题04.05：合法二叉搜索树");
        System.out.println("面试题04.06：后继者");
        System.out.println("面试题04.08：首个共同祖先");
        System.out.println("面试题04.09：二叉搜索树序列");
        System.out.println("面试题04.10：检查子树");
        System.out.println("面试题04.12：求和路径");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Interview_04_01{
    Set<Integer>[] adjacentArr;
    boolean[] visiable;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        adjacentArr = new Set[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new HashSet<Integer>();
        }
        for (int[] edge : graph) {
            if (edge[0] != edge[1]) {
                adjacentArr[edge[0]].add(edge[1]);
            }
        }
        visiable = new boolean[n];
        return process(start, target);
    }

    public boolean process(int vertex, int target) {
        visiable[vertex] = true;
        if (!visiable[target]) {
            Set<Integer> adjacent = adjacentArr[vertex];
            for (int next : adjacent) {
                if (!visiable[next] && process(next, target)) {
                    return true;
                }
            }
        }
        return visiable[target];
    }
}

class Interview_04_02{
    public TreeNode process(int[] nums,int start,int end) {
        if (start==end) {//仅一个节点的结构
            return new TreeNode(nums[start]);
        }else if (end-start==1) {//仅两个节点的结构
            TreeNode min=new TreeNode(nums[start]),max=new TreeNode(nums[end]);
            max.left=min;
            return max;
        }
        int mid=0;
        if ((end-start+1)%2==0) {
            mid=(end+start)/2+1;
        }else {
            mid=(end+start)/2;
        }
        TreeNode curNode=new TreeNode(nums[mid]);//划分左右子树
        curNode.left=process(nums,start,mid-1);
        curNode.right=process(nums,mid+1,end);
        return curNode;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length==0) return null;
        return process(nums,0, nums.length-1);
    }
}

class Interview_04_03{
    public ListNode process(List<Integer> list) {//构造层链表
        ListNode vir=new ListNode(0),temp=vir;
        for (int num:list) {
            ListNode cur=new ListNode(num);
            temp.next=cur;
            temp=temp.next;
        }
        return vir.next;
    }
    public ListNode[] listOfDepth(TreeNode tree) {
        List<List<Integer>> lists=new ArrayList<>();
        Deque<TreeNode> deque=new LinkedList<>();
        if (tree!=null) {
            deque.add(tree);
            int curCount=1,nextCount=0;
            List<Integer> temp=new ArrayList<>();
            while (!deque.isEmpty()) {
                TreeNode treeNode = deque.pollFirst();//本层出队
                curCount--;
                temp.add(treeNode.val);
                if (treeNode.left!=null) {//子节点入队
                    deque.add(treeNode.left);
                    nextCount++;
                }
                if (treeNode.right!=null) {
                    deque.add(treeNode.right);
                    nextCount++;
                }
                if (curCount==0) {//换层
                    curCount=nextCount;
                    nextCount=0;
                    lists.add(temp);
                    temp=new ArrayList<>();
                }
            }
            ListNode[] result=new ListNode[lists.size()];
            for (int i=0;i<lists.size();i++){
                result[i]=process(lists.get(i));
            }
            return result;
        }else return new ListNode[0];
    }
}

class Interview_04_04{
    class Info{
        boolean isBalance;//是否平衡
        int maxDeep;//最大深度
        public Info(boolean isBalance,int maxDeep) {
            this.isBalance=isBalance;
            this.maxDeep=maxDeep;
        }
    }
    public Info process(TreeNode root) {
        if (root==null) return new Info(true,0);
        Info left = process(root.left);
        Info right = process(root.right);
        if (!(left.isBalance&&right.isBalance)) return new Info(false,0);//左右子树存在不平衡
        if (Math.abs(left.maxDeep- right.maxDeep)>1) return new Info(false,0);//左右子树高度差超过1
        int max= (left.maxDeep> right.maxDeep ? left.maxDeep : right.maxDeep)+1;
        return new Info(true,max);
    }
    public boolean isBalanced(TreeNode root) {
        return process(root).isBalance;
    }
}

class Interview_04_05{
    public boolean isValidBST(TreeNode root) {
        return process(root, null, null);
    }
    public boolean process(TreeNode node, Integer lower, Integer upper) {
        if (node == null) return true;
        int val = node.val;
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;
        if (!process(node.right, val, upper)) return false;
        if (!process(node.left, lower, val)) return false;
        return true;
    }
}

class Interview_04_06{
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode result=null;
        boolean flag=false;
        while (root!=null||!stack.isEmpty()) {
            if (root!=null) {
                stack.push(root);
                root= root.left;
            }else {
                root=stack.pop();
                if (root==p||flag) {//中序至目标节点
                    if (root==p) flag=true;
                    else {
                        result=root;
                        break;
                    }
                }
                root= root.right;
            }
        }
        return result;
    }
}

class Interview_04_08{
    public class Info{
        public boolean isExistNode1;
        public boolean isExistNode2;
        public TreeNode commonFather;
        public Info(boolean isExistNode1, boolean isExistNode2, TreeNode commonFather){
            this.isExistNode1=isExistNode1;
            this.isExistNode2=isExistNode2;
            this.commonFather=commonFather;
        }
    }
    public Info process(TreeNode root, TreeNode p, TreeNode q){
        if (root==null) return new Info(false,false,null);
        Info left=process(root.left, p, q);//左子树信息
        Info right=process(root.right, p, q);//右子树信息
        if (left.commonFather!=null||right.commonFather!=null){//其中一个子树中已经存在公共祖先
            return left.commonFather==null ? right : left;//将存在公共祖先的子树信息返回
        }
        boolean node1=false,node2=false;
        TreeNode temp=null;
        if (root==p|| left.isExistNode1==true || right.isExistNode1==true) node1=true;//当其中一个子树中存在p或当前节点为p
        if (root==q|| left.isExistNode2==true || right.isExistNode2==true) node2=true;//当其中一个子树中存在q或当前节点为q
        if (node1&&node2){//当本节点即为公共祖先时
            temp=root;
        }
        return new Info(node1,node2,temp);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).commonFather;
    }
}

class Interview_04_09{
//    List<List<Integer>> levels,lists;
//    public void process(int index,List<Integer> lastList) {
//        ArrayList<Integer> curList=new ArrayList<>(lastList);
//        if (index==levels.size()) {
//            lists.add(curList);
//            return;
//        }
//        ArrayList<Integer> temp=new ArrayList<>(levels.get(index));
//        if (temp.size()>1) {
//            curList.addAll(temp);//正序添加
//            process(index+1,curList);
//            curList.removeAll(temp);//撤销正序添加
//            Collections.reverse(temp);//逆序添加
//            curList.addAll(temp);
//            process(index+1,curList);
//        }else {
//            curList.addAll(temp);
//            process(index+1,curList);
//        }
//    }
//    public List<List<Integer>> BSTSequences(TreeNode root) {
//        levels=new ArrayList<>();
//        Deque<TreeNode> deque=new LinkedList<>();
//        if (root!=null) {
//            deque.add(root);
//            int curCount = 1, nextCount = 0;
//            List<Integer> temp = new ArrayList<>();
//            while (!deque.isEmpty()) {
//                TreeNode treeNode = deque.pollFirst();//本层出队
//                curCount--;
//                temp.add(treeNode.val);
//                if (treeNode.left != null) {//子节点入队
//                    deque.add(treeNode.left);
//                    nextCount++;
//                }
//                if (treeNode.right != null) {
//                    deque.add(treeNode.right);
//                    nextCount++;
//                }
//                if (curCount == 0) {//换层
//                    curCount = nextCount;
//                    nextCount = 0;
//                    levels.add(temp);
//                    temp = new ArrayList<>();
//                }
//            }
//        }
//        lists=new ArrayList<>();
//        List<Integer> temp=new ArrayList<>();
//        process(0,temp);
//        return lists;
//    }
    List<List<Integer>> result;
    public List<List<Integer>> BSTSequences(TreeNode root) {
        this.result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root == null) {
            this.result.add(path);
            return this.result;
        }

        path.add(root.val);
        List<TreeNode> content = new LinkedList<>();
        if(root.left != null) content.add(root.left);
        if(root.right != null) content.add(root.right);

        process(content, path);
        return this.result;
    }

    public void process(List<TreeNode> content, List<Integer> path) {
        if(content.isEmpty()) {
            this.result.add(new ArrayList<>(path));
            return ;
        }
        List<TreeNode> temp = new ArrayList<>(content);
        for(int i = 0; i < content.size(); i++) {
            TreeNode node = content.get(i);
            path.add(node.val);
            content.remove(i);
            if(node.left != null) content.add(node.left);
            if(node.right != null) content.add(node.right);
            process(content, path);
            path.remove(path.size()-1);
            content = new ArrayList<>(temp);
        }
    }
}

class Interview_04_10{
    StringBuffer str1=new StringBuffer(),str2=new StringBuffer();
    public void process(TreeNode root,int flag) {
        if (root==null) {
            if (flag==1) str1.append("#");
            else str2.append("#");
            return;
        }else {
            process(root.left,flag);
            if (flag==1) str1.append(root.val);
            else str2.append(root.val);
            process(root.right,flag);
        }
    }
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        process(t1,1);//序列化二叉树
        process(t2,2);
        String s1=str1.toString(),s2=str2.toString();
        return s1.contains(s2);
    }
}

class Interview_04_12{
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return process(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int process(TreeNode node, int sum) {
        if (null == node) return 0;
        sum -= node.val;
        int count = sum == 0 ? 1 : 0;
        count += process(node.left, sum);
        count += process(node.right, sum);
        return count;
    }
}